package org.algorithm.二师兄.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;

/**
 * @Date 2022/2/27
 * @Link {https://leetcode-cn.com/problems/merge-k-sorted-lists/}
 */
public class 合并K个升序链表 {


    
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0){
            return null;
        }
        ListNode node = null;
        for (int i = 0; i <lists.length ; i++) {
                node = merge2Lists(lists[i],node);
        }
        return node;
    }
    public ListNode merge2Lists(ListNode node1,ListNode node2){
        if(node1==null && node2 == null){
            return null;
        }
        if(node1==null || node2==null ){
            return node1==null?node2:node1;
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode pre = dummyNode;
        ListNode p1 = node1;
        ListNode p2 = node2;
        while (p1!=null&&p2!=null){
            if(p1.val<p2.val){
                pre.next = p1;
                p1=p1.next;
            }else {
                pre.next = p2;
                p2 = p2.next;
            }
            pre = pre.next;
        }
        pre.next = p1==null?p2:p1;
        return dummyNode.next;
    }




}
